class Node:
    """二叉搜索树节点类"""

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    """二叉搜索树类"""

    def __init__(self):
        self.root = None

    def insert(self, value):
        """插入节点"""
        if not self.root:
            self.root = Node(value)
        else:
            self.add(self.root, value)

    def add(self, node, value):
        """递归插入辅助函数"""
        if value < node.value:
            # 值 小于当前树的 根节点，左子树不存在就赋值给左子树，存在递归到下一个左子树
            if node.left is None:
                node.left = Node(value)
            else:
                self.add(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                self.add(node.right, value)
        # 如果值已存在，可以选择不插入或更新 == 的情况

    def search(self, value):
        """查找节点"""
        return self.search_f(self.root, value)

    def search_f(self, node, value):
        """递归查找辅助函数"""
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            # 递归查找左节点
            return self.search_f(node.left, value)
        else:
            # 递归查找右节点
            return self.search_f(node.right, value)

    def delete(self, value):
        """删除节点"""
        self.root = self.delete_f(self.root, value)

    def delete_f(self, node, value):
        """递归删除辅助函数"""
        if node is None:
            return node

        if value < node.value:
            node.left = self.delete_f(node.left, value)
        elif value > node.value:
            node.right = self.delete_f(node.right, value)
        else:
            # 找到要删除的节点
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                # 有两个子节点的情况，找到右子树的最小节点
                min_node = self.find_min(node.right)
                # 赋值当前节点的值 为 找到的右子树最小节点的值
                node.value = min_node.value
                # 删除右子树中最小的值
                node.right = self.delete_f(node.right, min_node.value)
        return node

    def find_min(self, node):
        """找到子树中的最小节点"""
        # 一直遍历左节点即可
        while node.left is not None:
            node = node.left
        return node

    def ino(self, node):
        """递归中序遍历辅助函数"""
        if node is None:
            return []
        return self.ino(node.left) + [node.value] + self.ino(node.right)

    def pre(self, node):
        """递归前序遍历辅助函数"""
        if node is None:
            return []
        return [node.value] + self.pre(node.left) + self.pre(node.right)

    def post(self, node):
        """后序遍历"""
        if node is None:
            return []
        return self.post(node.left) + self.post(node.right) + [node.value]

    def height(self, node):
        """递归计算高度辅助函数"""
        if node is None:
            return 0
        return max(self.height(node.left), self.height(node.right)) + 1

    def width(self):
        """计算树的宽度"""
        if not self.root:
            return 0
        max_width = 0
        queue = [self.root]
        while queue:
            # 当前节点的数量
            level_size = len(queue)
            # 更新最大值
            max_width = max(max_width, level_size)
            # 遍历当前所有节点
            for _ in range(level_size):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return max_width


# 示例用法
if __name__ == "__main__":
    bst = BinarySearchTree()
    nums = [50, 30, 70, 20, 40, 60, 80]
    for num in nums:
        bst.insert(num)

    print("中序遍历:", bst.ino(bst.root))  # 输出排序后的结果
    print("前序遍历:", bst.pre(bst.root))
    print("后序遍历:", bst.post(bst.root))
    print("树的高度:", bst.height(bst.root))
    print("树的宽度:", bst.width())

    print("查找40:", bst.search(40))  # True
    print("查找45:", bst.search(45))  # False

    print("删除30:")
    bst.delete(30)
    print("中序遍历:", bst.ino(bst.root))
    print("树的高度:", bst.height(bst.root))
    print("树的宽度:", bst.width())